package com.shuzijun.leetcode.editor.cn;
public class BestTimeToBuyAndSellStock{
    public static void main(String[] args) {
         Solution solution = new BestTimeToBuyAndSellStock().new Solution();
         solution.maxProfit(new int[]{7,1,5,3,6,4});
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        public int maxProfit(int[] prices) {
            int n = prices.length;
            int[] max = new int[n];

            int curMax = 0;
            for (int i = n-1; i >= 0; i--) {
                max[i] =  curMax;
                if (prices[i] > curMax) curMax= prices[i];
            }


            int result = 0;
            for (int i = 0; i < n; i++) {
                if (result < max[i] - prices[i]){
                    result = max[i] - prices[i];
                }
            }
            return result;
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}